package 算法.回溯法.n皇后问题;

//import netscape.security.UserTarget;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;


public class N皇后问题_满n叉树 {
        public static void main(String[] args) {
            System.out.print("N皇后问题得N的个数：");
            Scanner scanner = new Scanner(System.in);
            int Q = scanner.nextInt();
            int[][] dp=new int[Q][Q];
            int i,j;
            //初始化
            for(i=0;i<Q;i++)
            {
                for(j=0;j<Q;j++)
                {
                    dp[i][j]=0;
                }
            }
            que(0,dp,Q);
        }

        private static void que(int m, int[][] dp,int Q) {
            ArrayList<String> arrayList=new ArrayList<>();
            if(m==Q){//递归结束条件
                //结束之后打印位置
                for(int i=0;i<Q;i++)
                {
                    for(int j=0;j<Q;j++)
                    {
                        if (dp[i][j]==1){
                            arrayList.add("("+i+","+j+")");
                           // System.out.println("("+i+","+j+")");
                        }
                        System.out.print(dp[i][j]+" ");
                    }
                    System.out.println("\n");
                }
                System.out.println(arrayList.toString());
                System.out.println("**********************");
            }
            //递归计算
            for(int i=0;i<Q;i++)
            {
                if (isCorrt(i,m,dp,Q)) {
                    dp[i][m]=1;
                    que(m+1, dp,Q);
                    dp[i][m]=0;
                }
            }
        }
        //判断这个位置能不能放皇后
        private static boolean isCorrt(int i, int j, int[][] dp,int Q) {
            // TODO Auto-generated method stub
            int s, t;  //s代表行,t代表列
            for(s=i,t=0; t<Q; t++)
                if(dp[s][t]==1 && t!=j)
                    return false;//判断行
            for(t=j,s=0; s<Q; s++)
                if(dp[s][t]==1 && s!=i)
                    return false;//判断列
            for(s=i-1,t=j-1; s>=0&&t>=0; s--,t--)
                if(dp[s][t]==1)
                    return false;//判断左上方
            for(s=i+1,t=j+1; s<Q&&t<Q;s++,t++)
                if(dp[s][t]==1)
                    return false;//判断右下方
            for(s=i-1,t=j+1; s>=0&&t<Q; s--,t++)
                if(dp[s][t]==1)
                    return false;//判断右上方
            for(s=i+1,t=j-1; s<Q&&t>=0; s++,t--)
                if(dp[s][t]==1)
                    return false;//判断左下方
            return true;
        }


}
